\subsection{Nested Linked List Searcher}

The nested linked list data structure is also a linked list, but contains a pointer towards a URL list, which is a new type of linked list. 
The URL list is used to store the URLs of pages the word has been found. It also
contains an integer indicating the number of occurrences the word has been found
on the page and a pointer towards the next URL list element. \\
Figure \ref{nestedlinkedlistfigure1} shows an example of a nested linked list.
\\
\begin{figure}
\begin{center}
\includegraphics[scale=1.0]{../Searchers/nestedlinkedlistfigure1.pdf}
\end{center}
\caption{Example of a nested linked list \label{nestedlinkedlistfigure1}}
\end{figure} 
To create a new element in the nested linked list the \texttt{put(String key,
String value)} method is called with both a word (\texttt{key}) and a URL (\texttt{value}).\\
Each time a new element is added to the nested linked list you will need to run
through the list until you either find the word or get to the end of the list.\\
The method assigns the current nested linked list element to the first element
in the list. See figure \ref{nested63-66} for the actual \texttt{java} code.
\\
\begin{figure}
\lstinputlisting[firstline=63,lastline=66,firstnumber=63]{../../src/model/searchers/advancedSearchers/nestedLinkedListSearcher/NestedLinkedListSearcher.java}
\caption{Sets current to first element (from \texttt{nestedLinkedListSearcher}
63-66)\label{nested63-66}}
\end{figure}
\\
It then checks if the first element contains data. If it does contain data the
nested linked list is looped through searching for the word (\texttt{key}. See
figure \ref{nested67-69} for the actual \texttt{java} code.
\\
\begin{figure}
\lstinputlisting[firstline=67,lastline=69,firstnumber=67]{../../src/model/searchers/advancedSearchers/nestedLinkedListSearcher/NestedLinkedListSearcher.java}
\caption{Checks if first element contains data (from
\texttt{nestedLinkedListSearcher} 67-69)\label{nested67-69}}
\end{figure}
\\
If neither the word nor the page exist then both needs to be added.  A nested
linked list element is created at the start of the nested linked list and a
related URL list element is created and the nested linked list pointed towards
this. See figure \ref{nested70-76} for the actual \texttt{java} code.
\\
\begin{figure}
\lstinputlisting[firstline=70,lastline=76,firstnumber=70]{../../src/model/searchers/advancedSearchers/nestedLinkedListSearcher/NestedLinkedListSearcher.java}
\caption{Creates a new element if no match (from
\texttt{nestedLinkedListSearcher} 70-76)\label{nested70-76}}
\end{figure}
\\
If you find the word you then need to run through the linked URL list until you
find the page or get to the end of the URL list. See figure \ref{nested77-79} for the actual \texttt{java} code.
\\
\begin{figure}
\lstinputlisting[firstline=77,lastline=79,firstnumber=77]{../../src/model/searchers/advancedSearchers/nestedLinkedListSearcher/NestedLinkedListSearcher.java}
\caption{Runs through the URL list(from
\texttt{nestedLinkedListSearcher} 77-79)\label{nested77-79}}
\end{figure}
\\
If you find the word and the page you wish to add, you increment the number of
occurrences of the word on the page. See figure \ref{nested80-82}
for the actual \texttt{java} code and figure \ref{nestedlinkedlistfigure2}
for a grafical representation of where the incrementing takes place.
\begin{figure}
\lstinputlisting[firstline=80,lastline=82,firstnumber=80]{../../src/model/searchers/advancedSearchers/nestedLinkedListSearcher/NestedLinkedListSearcher.java}
\caption{Increments occurrences if URL found(from
\texttt{nestedLinkedListSearcher} 80-82)\label{nested80-82}}
\end{figure}
\\
\begin{figure}
\begin{center}
%nested linked list figure 2
\includegraphics[scale=1.0]{../Searchers/nestedlinkedlistfigure2.pdf}
\end{center} 
\caption{Shows where the increment takes places \label{nestedlinkedlistfigure2}}
\end{figure}  
\\
If you do not find the page, you need to add it to the start of the URL list.
See figure \ref{nested83-87} for the actual \texttt{java} code.
\\
\begin{figure}
\lstinputlisting[firstline=83,lastline=87,firstnumber=83]{../../src/model/searchers/advancedSearchers/nestedLinkedListSearcher/NestedLinkedListSearcher.java}
\caption{Increments occurrences if URL found(from
\texttt{nestedLinkedListSearcher} 83-87)\label{nested83-87}}
\end{figure}
\\
Figure \ref{createurllist} shows the new URL list element being
created and pointed towards the first URL list element in the list. Afterwards
the nested linked list is pointed towards the new URL list element, making that
the first one in the list.
\\
\begin{figure}
\centering
\subfloat[A new URL list element is
created]{\includegraphics[scale=0.8]{../Searchers/nestedlinkedlistfigure3.pdf}}
\hspace{10}
\subfloat[The nested linked list is being pointed towards the new URL
list]{\includegraphics[scale=0.8]{../Searchers/nestedlinkedlistfigure4.pdf}} \caption{Creating a new URL element and pointing the nested linked list towards
the new element
\label{createurllist}}
\end{figure}  
\\ 
The nested linked list's \texttt{put} method is a much more time consuming
process than the linked list's \texttt{put} method, where you just add the
word at the end of the line no matter what. In the linked list you only
needed a word, but in the nested linked list you need both a word and a URL in
the nested linked list. This makes it possible to add a single element later on to the
 nested linked list data structure. In that linked list you can only add a
 series of words beginning with an URL (\texttt{"*PAGE:"}) or you could get
 incoherent data, i.e. the last URL in the linked list will be the URL of the new words.\\
\\
When searching for a word in the nested linked list, the
list is looped through in the same manner as with a linked list. But if
the word is found, the loop stops and returns the URL list with the URLs of the
word. This makes the data structures much more efficient than the linked list as the
\texttt{get} method does not need to run to the end of the list in all cases,
but only if the word is not found or the word is at the end of the list. This
makes the approximated time needed for a search half of the time needed to
search in a basic linked list, as it on average only needs to run to the
middle of the list.

